##案例###
m = 1
n = 3
maxMove = 3
startRow = 0
startColumn = 1
# m = 2
# n = 2
# maxMove = 2
# startRow = 0
# startColumn = 0
#方法1：记忆化搜索
direction=[-1,0,1,0,-1]
def dfs(m,n,maxMove,startRow,startColumn,cache):
    #一种情况
    if maxMove==0:
        #没有移动步数了
        cache[startRow*n+startColumn][0]=0
        return 0
    if cache[startRow*n+startColumn][maxMove]!=-1:
        return cache[startRow*n+startColumn][maxMove]
    if maxMove==1:
        count=0
        for k in range(4):
            r,c=startRow+direction[k],startColumn+direction[k+1]
            if r<0 or r>=m or c<0 or c>=n:
                count+=1
        cache[startRow*n+startColumn][maxMove]=count
        return cache[startRow*n+startColumn][maxMove]
    count=0
    for k in range(4):
        x,y=startRow+direction[k],startColumn+direction[k+1]
        if x>=0 and x<m and y>=0 and y<n:
            #其边上一个位置的坐标是正常的坐标，表示其附近没有可以出界的位置
            count+=dfs(m,n,maxMove-1,x,y,cache)
        else:
            #不是正常的坐标，出界了
            count+=1
    count=int(count)%int(1e9+7)
    cache[startRow*n+startColumn][maxMove]=count
    return count
def findPaths(m,n,maxMove,startRow,startColumn):
    #做一个cache矩阵
    #横坐标是m*n(存放坐标位置)
    #纵坐标是移动步数
    cache=[[-1 for _ in range(maxMove+1)] for _ in range(m*n)]
    # print(cache)
    return dfs(m,n,maxMove,startRow,startColumn,cache)

##方法2：动态规划
def findPaths1(m,n,maxMove,startRow,startColumn):
    #dp状态转移矩阵
    dp=[[-1 for _ in range(maxMove+1)] for _ in range(m*n)]

    for i in range(m*n):
        #所有的移动步数为0的，可以出去的概率都是0
        dp[i][0]=0
    for move in range(1,maxMove+1):
        for i in range(m):
            for j in range(n):
                count=0
                for k in range(4):
                    r,c=i+direction[k],j+direction[k+1]
                    if r<0 or r>=m or c<0 or c>=n:
                        count+=1
                    else:
                        count+=dp[r*n+c][move-1]
                dp[i*n+j][move]=count
    return dp[startRow*n+startColumn][maxMove]


print(findPaths1(m,n,maxMove,startRow,startColumn))
